template <typename DT>
class DoubleLinkedList{
	private:

		//Nested Node class for List class
		struct Node{
			DT data;
			Node *prev;
			Node *next;

			//Creating a new Node
			Node( const DT & d = DT{}, Node *p = nullptr, Node *n = nullptr )
				: data{ d }, prev{ p }, next{ n } { }
			Node( DT && d, Node * p = nullptr, Node * n = nullptr )
				: data{ std::move( d ) }, prev{ p }, next{ n } { }
		};
	public:

		//Nested const_iterator class for List class
		class const_iterator{
			public:
				const_iterator() : current{ nullptr }
				{ }

				const DT & operator* () const{
					return retrieve();
				}

				const_iterator & operator++ (){
					current = current -> next;
					return *this;
				}

				const_iterator operator++ ( int ){
					const_iterator old = *this;
					++( *this );
					return old;
				}

				bool operator== ( const const_iterator & rhs ) const{
					return current == rhs.current;
				}

				bool operator!= ( const const_iterator & rhs ) const{
					return !( *this == rhs);
				}

			protected:
				Node *current;

				DT & retrieve() const{
					return current -> data;
				}

				const_iterator( Node *p ) : current{ p }{
				}

				friend class DoubleLinkedList<DT>;
		};
		
		class iterator : public const_iterator{
			public:
				iterator(){
				}

				DT & operator* ( ){
					return const_iterator ::retrieve( );
				}
				const DT & operator* () const{
					return const_iterator::operator*();
				}

				iterator & operator++ (){
					this -> current = this -> current -> next;
					return *this;
				}

				iterator operator++ ( int ){
					iterator old = *this;
					++( *this );
					return old;
				}

			protected:
				iterator( Node *p ) : const_iterator{ p }{
				}

				friend class DoubleLinkedList<DT>;
		};

	public:
		//Constructor and Big-Five for List class
		DoubleLinkedList(){
			init();
		}
		
		DoubleLinkedList( const DoubleLinkedList & rhs ){
			init();
			for( auto & x : rhs )
				push_back( x );
		}
		
		~DoubleLinkedList(){
			clear();
			delete head;
			delete tail;
		}
		
		DoubleLinkedList & operator= ( const DoubleLinkedList & rhs){
			DoubleLinkedList copy = rhs;
			std::swap( *this, copy );
			return *this;
		}
		
		DoubleLinkedList ( DoubleLinkedList && rhs )
			: theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }{
				rhs.theSize = 0;
				rhs.head = nullptr;
				rhs.tail = nullptr;
			}
		
		DoubleLinkedList & operator= ( DoubleLinkedList && rhs){
			std::swap( theSize, rhs.theSize );
			std::swap( head, rhs.head );
			std::swap( tail, rhs.tail );
			return *this;
		}
		
		
		iterator begin(){
			return { head -> next };
		}
		const_iterator begin() const{
			return { head -> next };
		}
		iterator end(){
			return { tail };
		}
		const_iterator end() const{
			return { tail };
		}
		
		
		int size() const{
			return theSize;
		}
		bool empty() const{
			return size() == 0;
		}
		
		
		void clear(){
			while(!empty())
				pop_front();
		}
		
		
		DT & front(){
			return *begin();
		}
		const DT & front() const{
			return *begin();
		}
		DT & back(){
			return *--end();
		}
		const DT & back() const{
			return *--end();
		}
		void push_front( const DT & x ){
			insert( begin(), x );
		}
		void push_front( DT && x){
			insert( begin(), std::move( x ) );
		}
		void push_back( const DT & x ){
			insert( end(), x );
		}
		void push_back ( DT  && x ){
			insert( end(), std::move( x ) );
		}
		void pop_front(){
			erase( begin() );
		}
		void pop_back(){
			erase( --end() );
		}
		
		// Insert x before itr.
		iterator insert( iterator itr, const DT & x ){
			//additioal error checks
			//itr.assertIsValid();
			//if( itr.theList != this )
				//throw IteratorMismatchEXception{ };


			Node *p = itr.current;
			theSize++;
			return { p -> prev = p -> prev -> next = new Node{ x, p -> prev, p } };
		}
		
		iterator insert( iterator itr, DT && x ){
			Node *p = itr.current;
			theSize ++;
			return { p -> prev = p -> prev -> next = new Node{ std::move( x ), p -> prev, p } };
		}

		// Erase item at itr.
		iterator erase( iterator itr ){
			Node *p = itr.current;
			iterator retVal{ p -> next };
			p -> prev -> next = p -> next;
			p -> next -> prev = p -> prev;
			delete p;
			theSize --;
			return retVal;
		}
		iterator erase( iterator from, iterator to ){
			for( iterator itr = from; itr != to; )
				itr = erase( itr );
			return to;
		}
	
	private:
		int theSize;
		Node *head;
		Node *tail;

		//private init routine for List class
		void init(){
                        theSize = 0;
                        head = new Node;
                        tail = new Node;
                        head -> next = tail;
                        tail -> prev = head;
                }





};
